package com.zfl;

public class MinWindow {

    public String minWindow(String s, String t) {

        if("".equals(t)||s.length()<t.length()) {
            return "";
        }

        int[] target = new int[128];
        int distinctT=0;
        for(char c:t.toCharArray()) {
            if(target[c]==0) {
                distinctT++;
            }
            target[c]++;
        }
        int left=0;
        int right=0;
        int minLen=Integer.MAX_VALUE;
        int start = 0;

        char[] chars = s.toCharArray();
        int[] current = new int[128];
        int match=0;
        while(right<chars.length)  {
            char c = chars[right];
            current[c]++;
            if(target[c]==current[c]) {
                match++;
            }
            right++;
            while(match==distinctT) {
                if(right-left<minLen) {
                    minLen=right-left;
                    start=left;
                }

                char leftChar = chars[left];
                current[leftChar]--;
                if(current[leftChar]<target[leftChar]) {
                    match--;
                }
                left++;
            }
        }
        return minLen==Integer.MAX_VALUE?"":s.substring(start,start+minLen);
    }
}
